package mtest3.day6;

import java.util.Arrays;
import java.lang.reflect.Array;

public class Demo2 {
    //归并排序
    public static void main(String[] args) {
        int[] arr = new int[]{11, 19, 5, 4, 7, 13, 2, 10, 30};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    public static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        //求中间索引
        int mid = (start + end) / 2;
        System.out.println("start=" + start + "end=" + end);
        //拆分成start到mid  和mid+1到end两部分
        mergeSort(arr, start, mid);//对start到mid 调用mergeSort 再次拆分
        mergeSort(arr, mid + 1, end);//对mid + 1到end 调用mergeSort 再次拆分
        merge(arr, start, mid, end);
    }


    //把 arr数组的  start到mid   mid+1到end                 [2,5,6,10,12,14   3,8,11,15,16,19,20]
    public static void merge(int[] arr, int start, int mid, int end) {

        //定义两个指针 i指向左侧部分（start到mid）数据的第一个  j指向右侧部分（mid+1到end）数据的第一个
        int i = start, j = mid + 1;

        int[] temp = new int[end - start + 1];//用来临时存放排好的数据

        int index = 0;

        //从左向右一个一个比对 小的加入到temp里
        while (i <= mid && j <= end) {

            if (arr[i] <= arr[j]) {
                temp[index++] = arr[i];
                i++;
            } else {
                temp[index++] = arr[j];
                j++;
            }
        }

        //把左半部分剩余数据添加到temp   有可能没有剩余
        while (i <= mid) {
            temp[index++] = arr[i++];
        }

        //把右半部分剩余数据添加到temp  有可能没有剩余
        while (j <= end) {
            temp[index++] = arr[j++];
        }

        //把temp里排序好的数据 一个一个填充回arr里对应的位置
        for (int k = 0; k < temp.length; k++) {
            //注意这里的加上start
            arr[start + k] = temp[k];
        }
    }
}
